package leetcode每日一题.leetcode20212;

/**
 * 1. 问题描述
 *      当 A的子数组A[i], A[i+1], ..., A[j]满足下列条件时，我们称其为湍流子数组：
 *      若i <= k < j，当k为奇数时，A[k] > A[k+1]，且当k为偶数时，A[k] < A[k+1]；
 *      或若i<=k<j，当k为偶数时，A[k]>A[k+1]，且当 k为奇数时，A[k] < A[k+1]。
 *      也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。
 *      返回A的最大湍流子数组的长度。
 *
 * 2. 算法分析
 *      1. 暴力法   时间复杂度O(n^2)  空间复杂度O(n)
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q007_最长湍流子数组 {

    /**
     * 暴力法   没有优化，存在冗余代码
     * @param arr
     * @return
     */
    public int maxTurbulenceSize1(int[] arr) {
        int n = arr.length; // 获取所有数组的长度
        if(n <= 1) {
            return 1;
        }
        int maxLen = 1; // 全局最大
        for(int i = 0; i < n - 1; i++) {
            if(arr[i] == arr[i+1]) {
                continue;
            }
            // 判断如果当前找到的maxLen已经大于从i到末尾的子数组的长度，此时就不需要在考虑了
            if(maxLen >= n - i) {
                break;
            }
            if(arr[i] < arr[i+1]) {
                boolean isRise = true;
                int curLen = 2;
                for(int j = i + 1; j < n -1; j++) {
                    if(arr[j] > arr[j+1] && isRise) {
                        curLen++;
                        isRise = !isRise;
                    } else if(arr[j] < arr[j+1] && !isRise) {
                        curLen++;
                        isRise = !isRise;
                    } else {
                        break;
                    }
                }
                maxLen = Math.max(maxLen,curLen);
            } else if(arr[i] > arr[i+1]) {
                boolean isRise = false;
                int curLen = 2;
                for(int j = i + 1; j < n -1; j++) {
                    if(arr[j] < arr[j+1] && !isRise) {
                        curLen++;
                        isRise = !isRise;
                    } else if(arr[j] > arr[j+1] && isRise) {
                        curLen++;
                        isRise = !isRise;
                    } else {
                        break;
                    }
                }
                maxLen = Math.max(maxLen,curLen);
            }
        }
        return maxLen;
    }

    /**
     * 优化上述的暴力法  逻辑没有变，但是简化了代码的书写，复杂度相同
     * @param arr
     * @return
     */
    public int maxTurbulenceSize2(int[] arr) {
        int n = arr.length; // 获取所有数组的长度
        if(n <= 1) {
            return 1;
        }
        int maxLen = 1; // 全局最大
        for(int i = 0; i < n - 1; i++) {
            if(arr[i] == arr[i+1]) {
                continue;
            }
            // 判断如果当前找到的maxLen已经大于从i到末尾的子数组的长度，此时就不需要在考虑了
            if(maxLen >= n - i) {
                break;
            }
            int curLen = 2;
            boolean isRise = (arr[i] < arr[i+1]) ? true : false;
            for(int j = i + 1; j < n - 1; j++) {
                if(arr[j] < arr[j+1] && !isRise) {
                    curLen++;
                    isRise = !isRise;
                } else if(arr[j] > arr[j+1] && isRise) {
                    curLen++;
                    isRise = !isRise;
                } else {
                    break;
                }
            }
            maxLen = Math.max(maxLen,curLen);
        }
        return maxLen;
    }


    /**
     * 动态规划  时间复杂度为O(n)  空间复杂度为O(n)
     * @param arr
     * @return
     */
    public int maxTurbulenceSize3(int[] arr) {
        int n = arr.length;
        if (n < 2) {
            return n;
        }
        // increased[i]表示以第i位结尾的下降的最长子数组的长度(arr[i] > arr[i-1])
        int[] increased = new int[n];
        // decreased[i]表示以第i位结尾的上升的最长子数组的长度(arr[i] < arr[i-1])
        int[] decreased = new int[n];
        // 初始化
        increased[0] = 1;
        decreased[0] = 1;
        // 设置结果变量
        int res = 1;        // 求解上述设置的dp数组
        for (int i = 1; i < n; i++) {
            // 上升
            if (arr[i] > arr[i-1]) {
                increased[i] = decreased[i-1] + 1;
                decreased[i] = 1; // 重置下降数组
            }
            // 下降
            else if (arr[i] < arr[i-1]) {
                decreased[i] = increased[i-1] + 1;
                increased[i] = 1; // 重置上升数组
            } else {
                // 重置
                increased[i] = 1;
                decreased[i] = 1;
            }
            res = Math.max(res,Math.max(decreased[i],increased[i]));
        }
        return res;
    }
}
